"""映射"""
from .exceptions import KeyErrorOfDataStructure, DataStructureIsEmpty
from .bst import AVLTree

class LinkedListMap:
    """
    @add    O(n)
    @remove    O(n)
    @set       O(n)
    @get       O(n)
    @contains   O(n)
    """
    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.next_node = None

    def __init__(self):
        self.dummy_head = LinkedListMap.Node(None, None)
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def get_node(self, key):
        """返回对应key的节点"""
        current = self.dummy_head.next_node
        while current is not None:
            if current.key == key:
                return current
            current = current.next_node
        return None

    def contains(self, key):
        return self.get_node(key) is not None

    def get(self, key):
        node = self.get_node(key)
        return node.val if node is not None else None

    def add(self, key, val):
        node = self.get_node(key)
        if node is None:
            new_node = LinkedListMap.Node(key, val)
            new_node.next_node = self.dummy_head.next_node
            self.dummy_head.next_node = new_node
            self._size += 1
        else:
            node.val = val

    def set(self, key, new_value):
        node = self.get_node(key)
        if node is None:
            raise KeyErrorOfDataStructure("Key does not exist.")
        else:
            node.val = new_value

    def remove(self, key):
        """删除对应key的val"""
        previous = self.dummy_head
        while previous.next_node is not None:
            if previous.next_node.key == key:
                break
            previous = previous.next_node
        if previous.next_node is not None:
            del_node = previous.next_node
            previous.next_node = del_node.next_node
            del_node.next_node = None
            self._size -= 1
            return del_node.val
        return None


class BSTMap:
    """
        平均为O(log(n))，最差情况为O(n)
        @add    O(h)   h为二分搜索树的高度，一般为log(n)
        @remove    O(h)
        @set       O(h)
        @get       O(h)
        @contains   O(h)
    """

    class Node:
        def __init__(self, key, val):
            self.key = key
            self.val = val
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None
        self._size = 0

    def size(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def add(self, key, val):
        """向map中添加映射关系"""
        self.root = self._add(self.root, key, val)

    def _add(self, node, key, val):
        if node is None:
            self._size += 1
            return BSTMap.Node(key, val)
        if node.key > key:
            node.left = self._add(node.left, key, val)
        elif node.key < key:
            node.right = self._add(node.right, key, val)
        else:
            # key相等，更新val的值
            node.val = val
        return node

    def get_node(self, node, key):
        """根据key找到对应的节点"""
        if node is None:
            return None
        if node.key == key:
            return node
        elif node.key > key:
            return self.get_node(node.left, key)
        else:
            return self.get_node(node.right, key)

    def contains(self, key):
        return self.get_node(self.root, key) is not None

    def get(self, key):
        node = self.get_node(self.root, key)
        return node.val if node is not None else None

    def set(self, key, new_value):
        node = self.get_node(self.root, key)
        if node is None:
            raise KeyErrorOfDataStructure("The key does not exist in the BSTMap.")
        node.val = new_value

    def _minimum(self, node):
        """返回二叉搜索树的最小节点"""
        if node.left is None:
            return node
        return self._minimum(node.left)

    def _remove_min(self, node):
        """删除二分搜索树的最小值，并返回删除最小值之后的二分搜索树的根节点"""
        if node.left is None:
            right_node = node.right
            node.right = None
            self._size -= 1
            return right_node
        node.left = self._remove_min(node.left)
        return node

    def remove(self, key):
        """
        @删除二分搜索树中键为key的节点
        @返回删除节点的val(没有时返回None)
        """
        node = self.get_node(self.root, key)
        if node is not None:
            self.root = self._remove(self.root, key)
            return self.root
        return None

    def _remove(self, node, key):
        """
        @删除二分搜索树中键为key的节点， 递归算法
        @返回删除节点后的新的二分搜索树的根节点
        """
        if node is None:
            return None
        if node.key > key:
            node.left = self._remove(node.left, key)
            return node
        elif node.key < key:
            node.right = self._remove(node.right, key)
            return node
        else:  # node.key == key
            if node.left is None:
                right_node = node.right
                node.right = None
                self._size -= 1
                return right_node
            elif node.right is None:
                left_node = node.left
                node.left = None
                self._size -= 1
                return left_node

            # 左右子树均不为空的情况， 用右子树的最小值替代要删除的那个节点，也可以用左子树的最大值替代
            successor = self._minimum(node.right)
            successor.right = self._remove_min(node.right)
            # self._size += 1  # 注意，这里由于删除的最小节点移动到前面去了，相当于没有删除，需要将_remove_min中的size减一操作撤销
            successor.left = node.left
            node.left = None   # 移除node，这里真正需要将size减一
            node.right = None
            # 前面size加一，后面size减一，所以抵消，全部注释掉，实际上相当一size减一，只不过是在_remove_min中完成的
            # self.size -= 1
            return successor


class AVLTreeMap:
    def __init__(self):
        self.tree = AVLTree()

    def __len__(self):
        return len(self.tree)

    def __contains__(self, item):
        return item in self.tree

    def add(self, key, val):
        self.tree.add(key, val)

    def get(self, key):
        return self.tree.get(key)

    def set(self, key, new_val):
        self.tree.set(key, new_val)

    def remove(self, key):
        return self.tree.remove(key)
